#include<cstring>
#include<iostream>
#include<cmath>
#include"graph.h"
#include"nodeList.h"
#include"node.h"

using namespace std;

/**
 * Létrehoz egy gráfot szomszédsági mátrix alapján (int* paraméterrel)
 *
 * @param mx A szomszédsági mátrix (alsó háromszögmátrix, sorfolytonosan)
 * @param size A mátrix mérete
 */
Graph::Graph(int* mx, int size)
{
    int t=size;
    int nodeCount=1;
    for(int i=1;(t-=i)>0;i++,nodeCount++);
    if(t)
        throw "Bad format";
    for(int i=0;i<nodeCount;i++)
    {
        this->nodes.addNode(new Node(i));
    }
    cout<<"Gyonyoruseges matrix:"<<endl;
    for(int i=0,j=0,k=0;i<size;i++,j++)
    {
        cout<<mx[i]<<" ";
        if(j>k)
        {
            k++;
            j=0;
        }
        if(i+1==((k+1)*(k+1)+(k+1))/2)cout<<endl;
        for(int l=0;l<mx[i];l++)
        {
            this->nodes[j]->addNeighbour(this->nodes[k]);
            if(j!=k)
            {
                this->nodes[k]->addNeighbour(this->nodes[j]);
            }
        }
    }
}

/**
 * Létrehoz egy gráfot szomszédsági mátrix alapján (szöveges mátrix)
 *
 * @param mx A szomszédsági mátrix (mezők vesszővel elválasztva, sorfolytonosan)
 */
Graph::Graph(char* mx)
{
    int mxSize=1;
    for(int i=0;mx[i];i++)
    {
        mxSize+=mx[i]==',';
    }
    int t=mxSize;
    for(int i=1;(t-=i)>0;i++);
    if(t)
        throw "Bad format";
    int* mx2=new int[mxSize];
    int i;
    for(int j=i=0;i<mxSize;i++,j++)
    {
        int k;
        for(k=0;mx[j]!=','&&mx[j];j++)
        {
            k*=10;
            k+=mx[j]-'0';
        }
        mx2[i]=k;
    }
    for(int i=0;i<(-1+sqrt(1+8*mxSize))/2;i++)
    {
        this->nodes.addNode(new Node(i));
    }
    cout<<"Gyonyoruseges matrix:"<<endl;
    for(int i=0,j=0,k=0;i<mxSize;i++,j++)
    {
        cout<<mx2[i]<<" ";
        if(j>k)
        {
            k++;
            j=0;
        }
        if(i+1==((k+1)*(k+1)+(k+1))/2)cout<<endl;
        for(int l=0;l<mx2[i];l++)
        {
            this->nodes[j]->addNeighbour(this->nodes[k]);
            if(j!=k)
            {
                this->nodes[k]->addNeighbour(this->nodes[j]);
            }
        }
    }
    delete[] mx2;
}

/**
 * A gráf destruktora
 */
Graph::~Graph()
{
    this->nodes.dropNodes();
}

/**
 * Megszámolja a gráf csúcsait
 * @return A gráf csúcsainak száma
 */
int Graph::getNodeCount()
{
    return this->nodes.getSize();
}

/**
 * Megszámolja a gráf éleinek a számát
 * @return A gráf éleinek száma
 */
int Graph::getEdgeCount()
{
    int s=0;
    for(int i=0;i<this->nodes.getSize();i++)
    {
        s+=this->nodes[i]->getDegree();
    }
    return s/2;
}

/**
 * Megállapítja a gráfról, hogy összefüggő-e (szélességi bejárással)
 *
 * Kezdetben hozzáadja egy NodeList-hez a 0. csúcsot, majd ezen a listán végighaladunk egy ciklussal,
 * minden ciklusban hozzáadjuk az aktuális csúcs szomszédait ehhez a listához (ha nem szerepel benne).
 * Ha a ciklus végére ennek a NodeList-nek a mérete megegyezik a gráf csúcsainak számával, akkor a gráf összefüggő.
 * @return Összefüggő-e a gráf
 */
bool Graph::bfSearch()
{
    NodeList queue;
    queue.addNode(new Node(this->nodes[0]->getId()));
    for(int i=0;i<queue.getSize();i++)
    {
        for(int k=0;k<this->nodes[queue[i]->getId()]->getNeighbours().getSize();k++)
        {
            if(!queue.nodeExists(this->nodes[queue[i]->getId()]->getNeighbours()[k]->getId()))
            {
                queue.addNode(new Node(this->nodes[queue[i]->getId()]->getNeighbours()[k]->getId()));
            }
        }
    }
    queue.dropNodes();
    if(queue.getSize()==this->nodes.getSize())
    {
        return true;
    }
    return false;
}
